package leetcode_400;

import java.util.HashMap;
import java.util.Stack;

/**
 *@author 周杨
 *LongestSubstringWithAtLeastKRepeatingCharacters_395_  寻找一个字符串的某个子串  这个子串一定是每个
 *字符出现次数都不小于k 而且长度是最大的
 *describe:用递归 首先 某个子串里只要字符小于k的一定不会出现在答案串里 那么以这种字符分割 得到字符串再递归 AC 61%
 *2018年7月14日 下午5:39:53
 */
public class LongestSubstringWithAtLeastKRepeatingCharacters_395_ {
	public int longestSubstring(String s, int k) {
		if(s == null || k<0) return 0;
        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
        for(int i=0; i<s.length(); i++){
            char c = s.charAt(i);
            if(hashmap.containsKey(c)){
                hashmap.put(c, hashmap.get(c)+1);
            } else {
                hashmap.put(c, 1);
            }
        }
        
        Character delimiter = null;
        for(Character c: hashmap.keySet()){
            if(hashmap.get(c)<k){
                delimiter = c;
            }
        }
        
        if(delimiter == null) {
            return s.length();
        }
        int maxlen = 0;
        String[] splits = s.split(""+delimiter);
        for(String str: splits){
            maxlen = Math.max(maxlen, longestSubstring(str,k));
        }
        return maxlen;
    }
}
